package List;

/**
 * 25.K个一组翻转链表
 * 给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
 * k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
 * 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
 */
public class reverseKGroup {

    /**
     * hot100一刷
     */
    public ListNode reverseKGroup(ListNode head, int k) {
        // 1. 判断剩余节点数是否有 k 个
        ListNode curr = head;
        int count = 0;
        while (curr != null && count < k) {
            curr = curr.next;
            count++;
        }

        // 若不足 k 个节点则直接返回，不进行翻转
        if (count < k) {
            return head;
        }

        // 2. 翻转当前 k 个节点
        //    prev 会成为翻转后子链表的新头结点
        ListNode prev = null;
        curr = head;
        for (int i = 0; i < k; i++) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }

        // 3. 递归翻转后续节点，并将本次翻转的尾结点与后续翻转结果连接
        head.next = reverseKGroup(curr, k);

        // 4. 返回翻转后的新头结点
        return prev;
    }


    /**
     * hot100二刷
     */
    public static ListNode reverseKGroup2(ListNode head, int k) {
        ListNode cur = head;
        int size = 0;
        while (cur != null) {
            cur = cur.next;
            size++;
        }
        if (size < k) {
            return head;
        }
        ListNode pre = null;
        ListNode post = null;
        cur = head;
        int count = k;
        while (cur != null && count > 0) {
            post = cur.next;
            cur.next = pre;
            pre = cur;
            cur = post;
            count--;
        }
        head.next = reverseKGroup2(cur, k);
        return pre;
    }


}
